#ifndef __SEQUENCESQUARE_H__
#define __SEQUENCESQUARE_H__
#include <vector>
using namespace std;

/*
* leetcode 977 有序数平方
* 要求在一个有序的数组中, 求出这个数组中元素的平方, 要求结果也有序
*/

/*
* 最简单的就是求出结果, 然后排序
* 这样的时间复杂度是 NlogN
*/

/*
* 这里使用双指针的思路:
* 例如: {-5, 1, 2, 3}
* return : {1, 4, 9, 25}
* 
* 根据输入数组的特点, 最大的结果肯定在两侧, 而最小的肯定在中间
* 使用双指针: 一个指向开头, 另一个指向结尾
*	然后不断向中间靠拢, 过程中比较两个指针平方后的大小, 放入结果数组的末尾
*/
vector<int> SequenceSquare(vector<int>& nums) {
	vector<int> results(nums.size(), 0);
	
	int left = 0, right = nums.size() - 1, pResult = nums.size() - 1;

	while (left < right) {
		int leftSquare = nums[left] * nums[left];
		int rightSquare = nums[right] * nums[right];
		if (leftSquare > rightSquare) {
			results[pResult] = leftSquare;
			left++;
		}

		else {
			results[pResult] = rightSquare;
			right--;
		}
		pResult--;
	}

	results[pResult] = nums[left] * nums[left];

	return results;
}

#endif // !__SEQUENCESQUARE_H__

